% !TEX root = sum1.tex
\clearpage
\section*{Proof}

\begin{pf}[Theorem 1]
At first, show $c_0(V,i)- c_0(V,i-1) < 0, i \in \{2,3,\ldots,v\}$, it is proven easily by the definition of $c_0(V,i) = \sum_{k=1}^{v} {\lceil k/i \rceil} t_{k}$.
Then we will prove $c_0 (V,i) - c_0 (V,i+1) < c_0 (V,i-1) - c_0 (V,i), i \in \{2,3,\ldots,v-1\}$, by discussing the ordinal number of $ $
  \qed
\end{pf}

\begin{pf}[Lemma 1]
The derivative of $\omega^*(P)$ is $m(V) - \sum_{s \in S} \rho_s \dots m^* $
  \qed
\end{pf}

\begin{pf}[Lemma 2]
  In fact, according to the SPT rule, a fixed number of using machines for the players in the grand coalition corresponds to the only deterministic working order on the machines. So the total cost is
  deterministic with the given processing times.
  Therefore, by comparing the cost of the number of adjacent machines $(k, k + 1)$ used by the grand coalition, the corresponding setup cost or the price $P_i$ can be obtained.

can be calculated with processing times $t_i$ by comparing the costs of the grand coalitions where all the players use two adjacent numbers of machines.
  \qed
\end{pf}

\begin{pf}[Theorem 1]

By deriving from $\omega^* (P)$ (\ref{dual}),it can be seen that the SPF $\omega(P)$ is in fact the point-wise maximum of a set of straight lines, $c_0(V)+m(V)P+\sum_{s\in S\setminus\{V\}}-\rho_s[c_0(s)+m(s)P]$, each with a slope of $m(V)+\sum_{s\in S\setminus\{V\}} −\rho_s m(s)$, for $\rho$ in $\{\rho :\sum_{s\in S\setminus \{V\}:k\in s} \rho_s=1\  \text{for all }  k\in V,\ \text{and } \rho_s \geq 0\ \text{for all } s\in S\setminus \{V\} \}$.
Meanwhile, it's easy to see that $m(s)$ does not increase as P increases. Thus, we can claim that the SPF $\omega(P)$ is a convex function in P when $m(V)$ is a fixed integer.

Notice that the existence of $m(V)$ does not affect the property of the numbers of the breakpoints.
% 注意这里还需要说明 [0,P*]
To show that the SPF $\omega^* (P)$ is a piecewise linear function with a ﬁnite number of breakpoints, consider the feasible region of LP (\ref{dual}) for $\omega^* (P)$ without the part of $m(V)$ that is written as $\acute{\omega} (P)$, which is a convex polyhedron, denoted by $\hat{R}$. It can be seen that $\hat{R}$ has a ﬁnite number of extreme points, and is independent of P. For any given $P \in [0,P^*]$, by LP (\ref{dual}) we know that there must exist an extreme point $\rho$ of $\hat{R}$ such that $\acute{\omega} (P)$ equals
$c_0(V)+m(V)P+\sum_{s\in S\setminus\{V\}}-\rho_s[c_0(s)+m(s)P]$
and that the derivative of $\acute{\omega} (P)$ at P equals $\sum_{s\in S\setminus\{V\}} −\rho_s m(s)$. Thus, the derivative of $\acute{\omega} (P)$ for $P \in [0,P^*]$ can have only a ﬁnite number of possible values. Moreover, due to the convexity of $\acute{\omega} (P)$, the derivative of $\acute{\omega} (P)$ is non-decreasing in P. Hence, the derivative of $\acute{\omega} (P)$ can change for only a ﬁnite number of times when P increases from 0 to $P^*$. Therefore, $\omega^* (P)$ is a piecewise linear function with a ﬁnite number of breakpoints.
\qed
\end{pf}


\begin{pf}[Theorem 2]

According to the foregoing description, we have the equation $P_{1}=P_{2}+\cdots+P_{v}=\sum_{i=2}^v P_i$.

For convenience of expression, we set the price as $P_{1},P_{2}, \dots ,P_{v}$ at interval extreme points while the number of machines used changes.
And $P_{i}$ denotes the price when the machine number changes from $i$ to $i-1$, especially, $P_{1}$ denotes the least price when number of machine used by the grand coalition is $1$ and the corresponding subsidy is $0$.
We just need to prove the following equality

\begin{displaymath}
  P_{1}=P_{2}+\cdots+P_{v}=\sum_{i=2}^n P_i.
\end{displaymath}

Notice that

\begin{displaymath}
  (n-1) \sum_{s \in S \setminus\{V\} } \rho_s \geq
  \sum_{k\in V}\sum_{s \in S \setminus\{V\}:k \in s} \rho_s = n.
\end{displaymath}

The left side of the inequality means for every $\rho_s$ can appear at most $(v-1)$ times, so we should know that if and only if for every $\rho_s > 0$ appears $v-1$ times the quality holds.That is to say, the coalitions which contains $v-1$ players are all maximally unsatisfied coalitions. Then we have $n \choose n-1$ equalities.
\[
\begin{cases}
 \alpha_1+\alpha_2+ \cdots+\alpha_{n-1} & = x_1 \\
 \alpha_1+\alpha_3+ \cdots+\alpha_n & = x_2 \\
 \quad   \vdots        &\vdots\\
 \alpha_2+\alpha_3+ \cdots+\alpha_n & = x_n.
\end{cases}
\]

Add these $n$ equations together, and we can get

\begin{equation*}
  (n-1)(\alpha_1+\alpha_2+ \cdots+\alpha_n)=\sum_{i=1}^{n}x_i
\end{equation*}

As we know, $x_1,x_2,\dots,x_n$ can be expressed as follows:

\[
\begin{cases}
x_1 = P_0 + (n-1)t_1 + (n-2)t_2 + &\cdots + t_{n-1} \\
x_2 = P_0 + (n-1)t_1 + (n-2)t_3 + &\cdots + t_{n-1} \\
\quad   \vdots        &\vdots\\
x_n = P_0 + (n-1)t_2 + (n-2)t_3 + &\cdots + t_{n}
\end{cases}
\]

According to SPT rule, we can obtain the equality
$c(V)=\alpha_1+\alpha_2+\cdots+\alpha_n=S_0+nt_1+(n-1)t_2+\dots+t_n$.
By replacing $x_1,x_2,\dots,x_n$ together with the expression of $c(V)$, we can get a equality only with $S_0,x_1,x_2,\dots,x_n$.

Finally, we can obtain $S_0 = \sum_{k=1}^n (n-k)t_k$.
\qed
\end{pf}

\begin{pf}[Theorem 3]
For the IPU game, when using $m$ machines is optimal, the setup cost $S_0$ must satisfies $t_m < S_0 < t_{m+1}$, which can be obtained from the process of calculating $S_k,~\frac{n}{2} < k \leq n$, where $S_k = t_{n-k+1}$.

When $m > \frac{n}{2}$, the optimal sequence which means the minimum cost is each of the $n-m$ machines has to process two jobs, while the rest $2m-n$ machines each with one job. We can find that there exists the following allocation which satisfies $\alpha(s) \leq c(s), s \in S:$
\[
\begin{aligned}
&\alpha(1)=2t_1,\alpha(2)=2t_2,\ldots,\alpha(n-m)=2t_{n-m},\ldots,\\
&\alpha(n-m+1)=S_0+t_{n-m+1},\ldots,\alpha(m)=S_0+t_{m},\ldots,\\
&\alpha(m+1)=S_0+t_{m+1},\ldots,\alpha(n)=S_0+t_n.\\
&\text{where} \ t_m < S_0 < t_{m+1}.
\end{aligned}
\]

Right now, $\alpha(1),\cdots,\alpha(n)$ can not be bigger any more. That is, $\mathop{max} \alpha(V) = c(V)$, then subsidy equals $c(V)-\alpha(V) = 0$.

%为了说明 满足所有的 不等式约束  必须从满足含有两个成员的不等式 推到 满足 任意多成员的不等式
\qed
\end{pf}


\begin{pf}[Theorem 4]
From (\ref{dual}), we know that the slope is $m(V)-\sum_{s\in S \setminus\{V\}} \rho_s \cdot m(s)$ when setup cost is $S_i$. At the left side of $S_i$, the number of using machines is $m(V)=i$ and the slope equals $i-\sum_{s\in S \setminus\{V\}} \rho_s \cdot m(s)$, which is positive, while at the right side of $S_i$, the number of using machines is $m(V)=i-1$ and the slope equals $\sum_{s\in S \setminus\{V\}} \rho_s \cdot m(s) - (i-1)$,
which is negative. So the sum of absolute values of slope on the left and right sides at $S_i$ is 1.
When $m(V)$ is 1, the expression of slope is $1-\sum_{s\in S \setminus\{V\}} \rho_s \cdot m(s)$. Meanwhile, $m(s) \leq m(V)$, so $m(s) = 1$, then the slope is $1-\sum_{s\in S \setminus\{V\}} \rho_s $.
Because we know that the sum of absolute values of slope at both sides of $S_2$ is 1, so the absolute value of the right side of slope less than 1.

From Theorem 1, we have:
\begin{displaymath}
    (n-1) \sum_{s \in S \setminus\{V\} } \rho_s \geq
    \sum_{k\in V}\sum_{s \in S \setminus\{V\}:k \in s} \rho_s = n
\end{displaymath}

$\sum_{s \in S \setminus\{V\}} \rho_s $ minimum is $\frac{n}{n-1}$，the corresponding maximum slope is $ 1-\sum_{s\in S \setminus\{V\}} \rho_s =-\frac{1}{n-1}$.

%注意断点的证明较复杂
\qed
\end{pf}

\begin{pf}[Theorem 5]
When the value of $P$ is between $(P_2,P_1)$, where the grand coalition only uses one machine, all the other sub-coalitions also use one machine. Now assume that the theorem is not tenable. When decreasing the value of $P$, for example, from $P_2$ to $P_3$. At some time, there must be such a situation that a sub-coalition denoted as $s'$ ($|s'| \geq 2 $) uses two machines which is optimal. Then we have $ \alpha(s') = c(s') +2P $ , there exist two coalitions $s_1,s_2$ which satisfy $ s_1 \cup s_2 = s',s_1 \cap s_2 = \emptyset $.
Meanwhile, $s_1,s_2$ also satisfy the two constraints $\alpha(s_1) \leq c(s_1) + P , \alpha(s_2) \leq c(s_2) + P $. Then we can obtain that $ c(s_1) + c(s_2) \geq c(s') $. At the same time, we know that the optimal sequence result shows $ c(s_1) + c(s_2) = c(s') $, which means the bigger coalition can be substituted by two smaller ones. Consequently, the coalitions $s$ only use one machine if the corresponding constraints are valid.
\qed
\end{pf}

\begin{pf}[Theorem 6]
The complexity of the whole problem can be divided into several stages, the first one is how to obtain the value  of $P_i$. For the IVPU game, the SPT rule can be used to calculate the $c(s)$. By sovling the last $n$ equalities, we can obtain $P_1$. Then we need to know the number of breakpoints, by IPC algorithm, we can construct the whole graph. Then the left problem is how to solve the slope in IPC algorithm, and how is the essential coalition set generated. The CP algorithm is used to obtain the subsidy and conclude a separation problem, if the separation problem can be solved easily, then the subsidy can be obtained easily.
Then we use DP algorithm to solve the separation problem and with the separation problem we can obtain the essential set. If the set is polynomial, we can calculate the slope by solving the LP.

\qed
\end{pf}

\begin{pf}[Lemma 2\&3]
As we all know, when $ P=0 $, it's optimal that every player in the coalition $s$ use one machine each.For the coalition $s$, when the price equals $P_m$, where the costs produced by the grand coalition are equal in value, the following formulas hold
$c(V,m)=c_0(s,m)+Pm, c(V,m-1)=c_0(s,m-1)+P(m-1)$ and $c(V,m)=c(V,m-1)$. Then we can obtain $P_m = c_0(V,m)- c_0(V,m-1), m=2,\ldots,n$.
Therefore, if $ c_0(V,m)- c_0(V,m-1) > 0 $, we can get $P_m > 0$.

Similarly, by substituting $m$ with $m+1$, we can obtain that $P_{m+1} = c_0(V,m+1)- c_0(V,m), m=2,3,\ldots,n$. If $c_0 (V,m) - c_0 (V,m+1) < c_0 (V,m-1) - c_0 (V,m)$, then $P_m < P_{m+1}, m=2,3,\ldots,n$.
\qed
\end{pf}

\begin{pf}[Theorem 7]

As we described before, the characteristic function $c(s,m(s,P))$ can be expressed as $c_0(s,m(s))+Pm$. For the two coalitions $s_1, s_2$, we use $c_0(s_2,m(s_1))$ to represent the cost produced by coaliton $s_2$ using $m(s_1)$ machines, where $m(s_1)$ is the number of machines used by coalition $s_1$ when the cost is minimum.

According to this definition and Lemma 2, obviously the following relation holds,
$c(s_1,m(s_1)) < c(s_1,m(s_1)-1) \Rightarrow c_0(s_1,m(s_1)-1)-c_0(s_1,m(s_1))>0$, because $c_0(s_1,m(s_1))$ is the minimum cost for $s_1$ using $m(s_1)$ machines.

For the two coalitions $s_1$, when the coalition $s_1$ uses $m(s_1)$ machines which is optimal, the following relation is established:
$m(s_1)P+c_0(s_1,m) < (m(s_1)-1)P+c_0(s_1,m-1) \Rightarrow P < c_0(s_1,m-1) - c_0(s_1,m)$.

When coalition $s_1$ uses $m(s_1)$, we assume that coalition $s_2$ uses $m(s_2)=m(s_1)-1<m(s_1)$ machines, which means $c(s_2,m(s_1)-1) < c(s_2,m(s_1))$. Then expand the formula, we obtain $P > c_0(s_2,m(s_1)-1)- c_0(s_2,m(s_1))$. However, because using $m(s_1)$ by coalition $s_1$ assures that $c(s_1,m(s_1)) < c(s_1,m(s_1)-1) \Rightarrow P < c_0(s_1,m(s_1)-1)-c_0(s_1,m(s_1))$.
So we can obtain that $ c_0(s_2,m(s_1)-1)- c_0(s_2,m(s_1)) <P <c_0(s_1,m(s_1)-1)-c_0(s_1,m(s_1))$, which contradicts the condition (\ref{concavity_f}).
With the result of that, we know $m(s_2) \neq m(s_1)-1$. \\
Meanwhile, according to the condition (\ref{property_p}) which tells us about the concavity of the number of machines. The larger the number of machines, the smaller the difference between these two items $c_0(s_1,m(s_1)-1)$ and $c_0(s_1,m(s_1))$. Take $m(s_2) = m(s_1)-2$ as an example, similar to the above, we can get $c(s_2,m(s_1)-2) < c(s_2,m(s_1)-1) \Rightarrow P > c_0(s_2,m(s_1)-2) - c_0(s_2,m(s_1)-1)$. According to the conditions (\ref{concavity_f}),
$c(s_1,m(s_1)) < c(s_1,m(s_1)-1) \Rightarrow P < c_0(s_1,m(s_1)-1)-c_0(s_1,m(s_1)) < c_0(s_1,m(s_1)-2)-c_0(s_1,m(s_1)-1) < c_0(s_2,m(s_1)-2) - c_0(s_2,m(s_1)-1)$ contradicts
$P > c_0(s_2,m(s_1)-2) - c_0(s_2,m(s_1)-1)$ we just obtained above.
Consequently, we know that $m(s_2)$ cannot be less than $m(s_1)-1$.
In conclusion, $m(s_1) \leq m(s_2)$.
% stated thus,to summarize,in summary, overall
% 注意这个证明  只与c_0(s) 有关
\qed
\end{pf}

\begin{pf}[Lemma 4]
With the $n$ equations for $\left| s \right|= n-1$ and $\alpha(V)=c_0(V)+P_1$, we can obtain the values of $\alpha(i)$. For each $\left| s' \right| < n-1$, suppose that $s'=\{i,\cdots,j\}$, we just need to prove:
\begin{equation} \label{lem2_1}
  \alpha(i,\cdots,j) \leq c_0(i,\cdots,j)+P_1
\end{equation}

Substitute $P_1=\alpha(V)-c(V)$ and $\alpha(i) = c(V)-c(-i)$ into the equation (\ref{lem2_1}), denote $c(-i)=c(\{1,\cdots,i-1,i+1,\cdots,n\})$, we just need to prove the following relation:
% let me plug in the values of a and b that will work.
\begin{equation}   \label{lem2_2}
  \sum_i^{N\setminus s'} c(-i) \leq (n-1-\left| s' \right|)c(V)+c(s')
\end{equation}

$\Rightarrow \qquad$

\begin{equation*}
  c(-k)-c(s') \leq (n-1-\left| s' \right|)c(V)-\sum_i^{N\setminus s'\setminus k} c(-i)
\end{equation*}

Because $c(s)$ satisfies the supermodular, we have the following set of inequalities.
\[
\begin{cases}
  c(V)-c(-t) \geq & c(-k)-c(-k-t) \\
  c(V)-c(-m) \geq & c(-k-t)-c(-k-t-m) \\
 \quad   \vdots        &\vdots\\
 c(V)-c(-s) \geq & c(s' \cup s)-c(s')
\end{cases}
\]
Add these $(n-1-\left| s' \right|)$ inequalities together, we can obtain $(n-1-\left| s' \right|)c(V)- \sum_i^{N\setminus s'} c(-i)+c(s') \geq 0 $. \\
That is, $\alpha(s') \leq c(s')+P_1, \forall s', \left|s' \right|<n-1$.
\qed
\end{pf}
